package 动态规划.组合求和系列;

import org.junit.Test;

import java.util.Scanner;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/22 22:22
 */
public class 新版本的组合求和 {

    /*
     以下来自 同盾科技 笔试第二题！
     给出一个 容量 为 v 的箱子，  给出一个物品数组 nums， nums[i] 表示 第i 号物品的体积.
     现在 往容量为 v, 的箱子中 装 物品, 请问, 箱子 最后 最小 还剩下多少 容量 ? (如果 刚刚好填满 箱子) 答案就是 0

     // 你发现无从下手, 所有有了 最下面 的暴力解法 , 能AC 单纯是因为,数据量非常的弱

     //  怎么去定义这个函数 f(index, rest)
     ①: 直接一步到位 定义:  f(index, rest) 表示 以index 开头进行决策, 剩余 rest 时, 最小剩余?
     你发现这样定义, 怎样去书写 这个 状态转移方程式呢 ?
     换一种 f()函数的定义函数
     ②: f(index ,rest) : 表示 的是 以index 开头, 进行决策, 剩余rest 时,的最大元素 和.
     那这个 状态转移 就比较 好写, 就是下面的写法,
     山重水复疑无路, 柳暗花明又一村! 的感觉!
    */


    public int recursion(int index,int rest,int nums[],Integer dp[][]) {
        if (index == nums.length || rest == 0) {
            return 0;
        }
        if (dp[index][rest] != null) {
            return dp[index][rest];
        }
        int ans = recursion(index + 1, rest, nums, dp);
        if (rest - nums[index] >= 0) {
            ans = Math.max(ans, recursion(index + 1, rest - nums[index], nums, dp) + nums[index]);
        }

        return dp[index][rest] = ans;
    }

    @Test
    public void tst(){
//        int nums[] = {3,7,8,7,12};
        int nums[] = {6,8,15,15,12,11};
        int target = 24;
        System.out.println(recursion(0,target,nums,new Integer[nums.length + 1][target + 1]));
    }



    // 暴力 dfs 直接 能 A 是我没有想到的

    public void solve1(){
        Scanner sc  = new Scanner(System.in);
        int v = sc.nextInt() , n = sc.nextInt();
        min = v;
        int nums[] = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
            sc.nextLine();
        }
        Integer dp[][] = new Integer[n + 1][v + 1];
        int recursion = recursion(0, v, nums, dp);
        if(recursion > 0){
            System.out.println(0);
            return ;
        }
        f(0,v,nums);
        System.out.println(min);

    }
    int min;
    public void f(int index,int rest,int nums[]){
        if(rest < 0 ){
            return ;
        }
        if(index == nums.length){
            if(rest >= 0){
                min = Math.min(min,rest);
            }
            return ;
        }
        f(index + 1,rest,nums);

        f(index + 1,rest - nums[index],nums);
    }



    public int recursionOne(int index,int rest,int nums[],Integer dp[][]){
        if(rest == 0){
            return 1;
        }
        if(dp[index][rest] != null){
            return dp[index][rest];
        }
        if(index == nums.length){
            return 0;
        }
        int ans = recursionOne(index + 1,rest,nums,dp);

        if(rest - nums[index] >= 0){
            ans += recursionOne(index + 1,rest - nums[index],nums,dp);

        }
        return dp[index][rest] = ans;
    }


}
